// 字典
class Dictionay {
	constructor() {
		this.items = {}
	}
	set(key, value) {
		this.items[key] = value
		return true
	}
	get(key) {
		if (this.has(key)) {
			return this.items[key]
		}
		return null
	}
	remove(key) {
		if (this.has(key)) {
			delete this.items[key]
			return true
		}
		return false
	}
	has(key) {
		return this.items.hasOwnProperty(key)
	}
	clear() {
		this.items = {}
	}
	size() {
		return Object.keys(this.items).length
	}
	values() {
		let values = []
		Object.keys(this.items).forEach((key) => {
			values.push(this.items[key])
		})
		return values
	}
	keys() {
		return Object.keys(this.items)
	}
}
// 队列
class Queue {
	constructor() {
		this.items = []
	}
	enquene(val) {
		this.items.push(val)
	}
	dequene() {
		return this.items.shift()
	}
	front() {
		return this.items[0]
	}
	isEnpty() {
		return this.items.length === 0
	}
	size() {
		return this.items.length
	}
	toString() {
		return this.items.join('').replace(/,/, '')
	}
}

let that
class Graph {
	constructor() {
		that = this
		this.vertex = []
		this.edges = new Dictionay()
	}
	addVertex(v) {
		this.vertex.push(v)
		this.edges.set(v, [])
	}
	addEdge(v1, v2) {
		this.edges.get(v1).push(v2)
		this.edges.get(v2).push(v1)
	}
	// 广度优先搜索
	bfs(v, handel) {
		let colors = initColor(this.vertex)
		let queue = new Queue()
		queue.enquene(v) // 队列思想
		while (!queue.isEnpty()) {
			let vertex = queue.dequene()
			let list = this.edges.get(vertex)
			colors[vertex] = 'gray'
			list.forEach((item) => {
				if (colors[item] === 'white') {
					colors[item] = 'gray'
					queue.enquene(item)
				}
			})
			handel(vertex)
			colors[vertex] = 'black'
		}
	}
	// 深度优先搜索
	dfs(v, handel) {
		let colorArr = initColor(this.vertex)
		dfsRecursion(v, handel, colorArr)
	}
	toString() {
		let str = ''
		this.vertex.forEach((key) => {
			let arr = []
			this.edges.get(key).forEach((element) => {
				arr.push(element)
			})
			str += `\n${key}==>${arr.join(' ')}\n`
		})

		return str
	}
}
// 广度优先算法辅助函数
function initColor(vertexAr = []) {
	let colorArr = []
	vertexAr.forEach((item) => {
		colorArr[item] = 'white'
	})
	return colorArr
}
// 深度优先算法辅助函数 ---递归实现
function dfsRecursion(v, handel, colorArr) {
	colorArr[v] = 'gray'
	handel(v)
	const list = that.edges.get(v)
	let i = 0
	while (i < list.length) {
		if (colorArr[list[i]] === 'white') {
			dfsRecursion(list[i], handel, colorArr)
		}
		i++
	}
	colorArr[v] = 'black'
}
